#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QueueNode;

typedef struct Queue
{
	QueueNode* phead;
	QueueNode* ptail;
	int size;
}Queue;

void QInit(Queue* q)
{
	assert(q);
	q->phead = q->ptail = 0;
	q->size = 0;
}

void QDesTory(Queue* q)
{
	assert(q);
	QueueNode* pcur = q->phead;
	while (pcur)
	{
		QueueNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	q->phead = q->ptail = NULL;
	q->size = 0;
}

void QPush(Queue* q, QDataType s)
{
	assert(q);
	QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newNode == NULL)
	{
		perror("malloc");
		exit(1);
	}
	newNode->next = NULL;
	newNode->data = s;
	if (q->phead == NULL)
	{
		q->phead = q->ptail = newNode;
	}
	else
	{
		q->ptail->next = newNode;
		q->ptail = q->ptail->next;
	}
	q->size++;
}

bool QEmpty(Queue* q)
{
	assert(q);
	return q->phead == NULL;
}
void QPop(Queue* q)
{
	assert(!QEmpty(&q));
	if (q->phead == q->ptail)
	{
		free(q->phead);
		q->phead = q->ptail = NULL;
	}
	else
	{
		QueueNode* next = q->phead->next;
		free(q->phead);
		q->phead = next;
	}
	q->size--;
}

QDataType QFront(Queue* q)
{
	assert(!QEmpty(q));
	return q->phead->data;
}

QDataType QBack(Queue* q)
{
	assert(!QEmpty(q));
	return q->ptail->data;
}
QDataType QSize(Queue* q)
{
	return q->size;
}


typedef struct {
	Queue q1;
	Queue q2;
} MyStack;


MyStack* myStackCreate() {
	MyStack* ps = (MyStack*)malloc(sizeof(MyStack));
	QInit(&ps->q1);
	QInit(&ps->q2);
	return ps;
}

void myStackPush(MyStack* obj, int x) {
	if (!QEmpty(&obj->q1))
	{
		QPush(&obj->q1, x);
	}
	else
	{
		QPush(&obj->q2, x);
	}
}

int myStackPop(MyStack* obj) {
	Queue* Empty = &obj->q1;
	Queue* NoneEmpty = &obj->q2;
	if (!QEmpty(&obj->q1))
	{
		NoneEmpty = &obj->q1;
		Empty = &obj->q2;
	}
	while (QSize(NoneEmpty) > 1)
	{
		QPush(Empty, QFront(NoneEmpty));
		QPop(NoneEmpty);
	}
	int a = QFront(NoneEmpty);
	QPop(NoneEmpty);
	return a;
}

int myStackTop(MyStack* obj) {
	if (!QEmpty(&obj->q1))
	{
		return QBack(&obj->q1);
	}
	else
	{
		return QBack(&obj->q2);
	}

}

bool myStackEmpty(MyStack* obj) {
	return QEmpty(&obj->q1) && QEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {
	QDesTory(&obj->q1);
	QDesTory(&obj->q2);
	free(obj);
	obj = NULL;
}

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);

 * int param_2 = myStackPop(obj);

 * int param_3 = myStackTop(obj);

 * bool param_4 = myStackEmpty(obj);

 * myStackFree(obj);
*/
